/*Davi Alves e Mariana Curi*/
#include <iostream>
#include <fstream>
#include <time.h>
#include <string>
#include <vector>

using namespace std;

#define CUTOFF 4
#define MAX_DIGITS 39555

int toInt(char param)
{
    int ret = param - '0';
    return ret;
}

char toChar(int param)
{
    char ret = '0' + param;
    return ret;
}

int* stringToIntArray(const string& param)
{
	int size = param.size();
	int arraySize = (size > MAX_DIGITS ? size * 3 : MAX_DIGITS);
	int* intArray = new int[arraySize]; 
	memset(intArray, 0, sizeof(int)*arraySize);

	for(int i = 0; i < size; i++){
		char tempChar = param[i];
		int tempInt = toInt(tempChar);
		intArray[i] = tempInt;
	}
	
	return intArray;
}

string* intArrayToString(int* a, int d){
    string* intToString = new string();
	char temp[MAX_DIGITS];
	int i;
    for (i = d - 1; i > 0; i--) 
	{
		if(a[i] != 0)
		{
			break;
		}
	}
    for (; i >= 0; i--)
	{
		memset(temp,0,sizeof(char)*MAX_DIGITS);
		sprintf(temp,"%d", a[i]);
		intToString->push_back( *temp );
	}
	return intToString;
}

void reverseNumber(int* number, int arraySize)
{
	int tempNumber;
    for (int i = 0; i*2 < ( arraySize - 1 ); i++) {
        tempNumber = number[i];
		number[i] = number[arraySize - i - 1];
		number[arraySize - i - 1] = tempNumber;
    }
}

void multiplication(int *a, int *b, int *ret, int d) {
    int             i, j;

    for(i = 0; i < 2 * d; i++) ret[i] = 0;
    for(i = 0; i < d; i++) {
        for(j = 0; j < d; j++) ret[i + j] += a[i] * b[j];
    }
}
int recursao = 0;
void karatsuba(int *a, int *b, int *ret, int d) {
    int             i;
    int             *ar = &a[0];
    int             *al = &a[d/2];
    int             *br = &b[0];
    int             *bl = &b[d/2];
    int             *asum = &ret[d * 5];
    int             *bsum = &ret[d * 5 + d/2];
    int             *x1 = &ret[d * 0];
    int             *x2 = &ret[d * 1];
    int             *x3 = &ret[d * 2];
	recursao++;
    if(d <= CUTOFF) {
        multiplication(a, b, ret, d);
        return;
    }

    for(i = 0; i < d / 2; i++) {
		int _al = al[i];
		int _ar = ar[i];
		int sumAlAr = _al + _ar;
        asum[i] =  sumAlAr;
		int _bl = bl[i];
		int _br = br[i];
		int sumBlBr = _bl + _br;
        bsum[i] = sumBlBr;
    }

    karatsuba(ar, br, x1, d/2);
    karatsuba(al, bl, x2, d/2);
    karatsuba(asum, bsum, x3, d/2);

    for(i = 0; i < d; i++) x3[i] = x3[i] - x1[i] - x2[i];
    for(i = 0; i < d; i++) ret[i + d/2] += x3[i];
}

void doCarry(int *a, int d) {
    int             c;
    int             i;
	int temp;
    c = 0;
    for(i = 0; i < d; i++) {
		if (d > 0) temp = a[i-1];
        a[i] += c;
        if(a[i] < 0) {
            c = -(-(a[i] + 1) / 10 + 1);
        } else {
            c = a[i] / 10;
        }
        a[i] -= c * 10;
    }
    if(c != 0) 
	{
		fprintf(stderr, "Overflow %d\n", c);
	}
}

// Voce deve escrever essa funcao!
string mul_rapido(const string& a, const string& b) {
	int* numberOneToIntArray = stringToIntArray(a);
    int* numberTwoToIntArray = stringToIntArray(b);
	int  numberOneLength = a.size();
	int  numberTwoLength = b.size();

    int maxLength;
    int  counter;

    counter = (numberOneLength > numberTwoLength) ? numberOneLength : numberTwoLength;
    for(maxLength = 1; maxLength < counter; maxLength *= 2);
	reverseNumber(numberOneToIntArray, numberOneLength);
	reverseNumber(numberTwoToIntArray, numberTwoLength);

	int*  result = new int[6 * maxLength];
	memset(result, 0, sizeof(int)*6 * maxLength);

	karatsuba(numberOneToIntArray, numberTwoToIntArray, result, maxLength);
	doCarry(result, 2 * maxLength);
	string* intToString = intArrayToString(result, 2 * maxLength);

	delete[] numberOneToIntArray;
	delete[] numberTwoToIntArray;
	delete[] result;

	return *intToString;
}
//ACABAM AQUI OS METODOS DA MULT RAPIDA-->

//AQUI COMECAM OS METODOS DA MULT LENTA<!--
// Voce deve escrever essa funcao!
string mul_lento(const string& a, const string& b) {
	int* numberOneToIntArray = stringToIntArray(a);
	int* numberTwoToIntArray = stringToIntArray(b);
	int*  result = new int[6 * MAX_DIGITS];
	int  numberOneLength = a.size();
	int  numberTwoLength = b.size();
	int  maxLength;
	int  counter;

	reverseNumber(numberOneToIntArray, numberOneLength);
	reverseNumber(numberTwoToIntArray, numberTwoLength);

	counter = (numberOneLength > numberTwoLength) ? numberOneLength : numberTwoLength;
	for(maxLength = 1; maxLength < counter; maxLength *= 2);

	multiplication(numberOneToIntArray, numberTwoToIntArray, result, maxLength);
	doCarry(result, 2 * maxLength);

	string* intToString = intArrayToString(result, 2 * maxLength);

	delete[] numberOneToIntArray;
	delete[] numberTwoToIntArray;
	delete[] result;
	return *intToString;
}
//ACABAM AQUI OS METODOS DA MULT LENTA-->

//AQUI COMECAM OS METODOS DA SOMA<!--
void completeZeros(string& a, string& b)
{
  int diff = (b.size() - a.size());
  char toFill = '0';
  if (diff > 0)
  {
    a.insert(a.begin(), diff, toFill);
  }
  if (diff < 0)
  {
    b.insert(b.begin(), (diff*(-1)), toFill);
  }
}

void deleteLeftZeros(string& str)
{
  if (str[0] == '0')
  {
    str = str.substr(str.find_first_not_of('0'));
  }
}

void removeOne(string& numberOne, int pos)
{
  if (numberOne[pos] == '0')
  {
    removeOne(numberOne, pos - 1);
    numberOne[pos] = '9';
    return;
  }
  numberOne[pos] = toChar(numberOne[pos] - '1');
}

string* sumPositiveValues(string& numberOne, string& numberTwo)
{
  int add = 0, sum = 0;
  string* result = new string();
  
  for (int i = (numberOne.size() -1); i >= 0; i--)
  {
    int numberOneInt = toInt(numberOne[i]);
    int numberTwoInt = toInt(numberTwo[i]);
    int individualSum = numberOneInt + numberTwoInt + add;

    add = individualSum / 10;
    sum = individualSum % 10;

    result->insert(result->begin(), 1, toChar(sum));
  }

  deleteLeftZeros(*result);
  
  return result;
}

string* sumNegativeValues(string& numberOne, string& numberTwo)
{
  string* result = new string();
  
  for(int i = (numberOne.size() -1); i >= 0; i--)
  {
    int numberOneInt = toInt(numberOne[i]);
    int numberTwoInt = toInt(numberTwo[i]);

    if(numberOneInt < numberTwoInt){
      numberOneInt = numberOneInt + 10;
      removeOne(numberOne,i - 1);
    }
    int subtraction = numberOneInt - numberTwoInt;

    result->insert(result->begin(), 1, toChar(subtraction));
  }   

  deleteLeftZeros(*result);
  
  return result;
}

bool isBigger(const string& numberOne, const string& numberTwo)
{
  bool isBigger = false;
  for (int i = (numberOne.size() - 1); i >= 0; i--)
  {
    if (toInt(numberOne[i]) > toInt(numberTwo[i]))
    {
      isBigger = true;
      continue;
    }
    isBigger = false;
  }
  return isBigger;
}

void checkForMinus(bool isNegative, string* str)
{
  if (isNegative)
  {
    str->insert(str->begin(), 1, '-');
  }
}

string* negativeBigger(string& numberOne, string& numberTwo, bool isOneNegative, bool isTwoNegative)
{
    string* result;

  if (isBigger(numberOne,numberTwo))
  {
    result = sumNegativeValues(numberOne, numberTwo);
    checkForMinus(isOneNegative,result);
  }
  else
  {
    result = sumNegativeValues(numberTwo, numberOne);
    checkForMinus(isTwoNegative,result);
  }

  return result;
}

bool doPositiveSum(bool isFirstNegative, bool isSecondNegative)
{
  return ((isFirstNegative && isSecondNegative) || (!isFirstNegative && !isSecondNegative));
}

bool isNumberNegative(const string& number)
{
  return (number[0] == '-');
}

string soma(string a, string b) {
    bool isANegative = isNumberNegative(a), isBNegative = isNumberNegative(b);
    
  if (isANegative)
  {
        a = a.substr(1);
    }
    if (isBNegative)
  {
        b = b.substr(1);
    }

  string result = "";
  completeZeros(a, b);
  if ( doPositiveSum(isANegative, isBNegative) )
  {
    result.append( *sumPositiveValues(a, b) );
    }
  else
  {
    result.append( *negativeBigger(a, b, isANegative, isBNegative) );
    }
  if ((isANegative && isBNegative))
  {
    result.insert(result.begin(), 1, '-');
  }
  return result;
}

//ACABAM AQUI OS METODOS DA SOMA-->

// Nao modifique nada daqui para baixo!
float nota = 0;

void testa_soma() {
    cout << "Testando soma. Quatro testes valendo 0.5 cada." << endl;
    
    if(soma("2","2") == "4") {
        nota += .5;
        cout << " Passou no teste 1 de soma." << endl;
    }
    if(soma("151115727451828646838272",
         "174449211009120179071170507") ==
         "174600326736572007718008779") {
        nota += .5;
        cout << " Passou no teste 2 de soma." << endl;
    }
    if(soma("-90","17") == "-73") {
        nota += .5;
        cout << " Passou no teste 3 de soma." << endl;
    }
    if(soma("1341068619663964900807",
             "-984770902183611232881") ==
             "356297717480353667926") {
        nota += .5;
        cout << " Passou no teste 4 de soma." << endl;
    }
}

void testa_mul_lento() {
    cout << "Testando multiplicacao quadratica. Cinco testes valendo 0.5 cada." << endl;
    
    ifstream f("teste-trab1.txt");
    string a, b, ab;
    int n;
    clock_t t;
    
    for(int i=1; i<=5; i++) {
        f >> a;
        f >> b;
        f >> ab;
        n = ab.length();
        t = clock();
 
        if(mul_lento(a, b) == ab) {
            nota += .5;

            cout << " Passou no teste "<< i << " de mul_lento (" << n << " algarismos) em "
                << (float)(clock() - t) / CLOCKS_PER_SEC
                << " segundos." << endl;
        }
    }
}

void testa_mul_rapido() {
    cout << "Testando multiplicacao sub-quadratica. Onze testes valendo 0.5 cada." << endl;
    
    ifstream f("teste-trab1.txt");
    string a, b, ab;
    int n;
    clock_t t;
    
    for(int i=1; i<=11; i++) {
        f >> a;
        f >> b;
        f >> ab;
        n = ab.length();
        t = clock();
 
        if(mul_rapido(a, b) == ab) {
            nota += .5;

            cout << " Passou no teste "<< i << " de mul_rapido (" << n << " algarismos) em "
                << (float)(clock() - t) / CLOCKS_PER_SEC
                << " segundos." << endl;
        }
    }
}

int main() {
    testa_soma();
    testa_mul_lento();
    testa_mul_rapido();
    cout << "Nota total: " << nota << endl;
	system("pause");
    return 0;
}
